package tree;

// 红黑树节点类
class RedBlackNode {
    int key;  // 节点的键
    RedBlackNode left, right, parent;  // 左、右子节点和父节点
    boolean color; // 节点的颜色，true 表示红色，false 表示黑色

    public RedBlackNode(int key) {
        this.key = key;
        this.left = this.right = this.parent = null;
        this.color = true; // 新插入的节点默认为红色
    }
}

// 红黑树类
public class RedBlackTree {
    private RedBlackNode root;
    private final RedBlackNode TNULL; // 哨兵节点，代表叶子节点

    public RedBlackTree() {
        TNULL = new RedBlackNode(0);
        TNULL.color = false; // TNULL 节点为黑色
        root = TNULL;
    }

    // 左旋转
    private void leftRotate(RedBlackNode x) {
        RedBlackNode y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // 右旋转
    private void rightRotate(RedBlackNode x) {
        RedBlackNode y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    // 插入新节点
    public void insert(int key) {
        RedBlackNode node = new RedBlackNode(key);
        node.left = TNULL;
        node.right = TNULL;

        RedBlackNode y = null;
        RedBlackNode x = root;

        // 找到插入位置
        while (x != TNULL) {
            y = x;
            if (node.key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node; // 新节点为根节点
        } else if (node.key < y.key) {
            y.left = node;
        } else {
            y.right = node;
        }

        if (node.parent == null) {
            node.color = false; // 根节点设为黑色
            return;
        }

        if (node.parent.parent == null) {
            return;
        }

        // 修复红黑树性质
        fixInsert(node);
    }

    // 修复插入后的红黑树性质
    private void fixInsert(RedBlackNode k) {
        while (k.parent.color == true) {
            if (k.parent == k.parent.parent.right) {
                RedBlackNode u = k.parent.parent.left; // 叔父节点
                if (u.color == true) {
                    // 情况1：叔父节点是红色
                    k.parent.color = false;
                    u.color = false;
                    k.parent.parent.color = true;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        // 情况2：节点是其父节点的左孩子
                        k = k.parent;
                        rightRotate(k);
                    }
                    // 情况3：节点是其父节点的右孩子
                    k.parent.color = false;
                    k.parent.parent.color = true;
                    leftRotate(k.parent.parent);
                }
            } else {
                RedBlackNode u = k.parent.parent.right; // 叔父节点

                if (u.color == true) {
                    // 情况1：叔父节点是红色
                    k.parent.color = false;
                    u.color = false;
                    k.parent.parent.color = true;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.right) {
                        // 情况2：节点是其父节点的右孩子
                        k = k.parent;
                        leftRotate(k);
                    }
                    // 情况3：节点是其父节点的左孩子
                    k.parent.color = false;
                    k.parent.parent.color = true;
                    rightRotate(k.parent.parent);
                }
            }
            if (k == root) {
                break;
            }
        }
        root.color = false;
    }

    // 中序遍历
    public void inOrderTraversal() {
        inOrderHelper(this.root);
    }

    private void inOrderHelper(RedBlackNode node) {
        if (node != TNULL) {
            inOrderHelper(node.left);
            System.out.print(node.key + " ");
            inOrderHelper(node.right);
        }
    }

    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        tree.insert(10);
        tree.insert(20);
        tree.insert(30);
        tree.insert(15);
        tree.insert(25);

        System.out.println("红黑树的中序遍历结果：");
        tree.inOrderTraversal();
    }
}
